"""
 格雷编码是一个二进制数字系统，在该系统中，两个连续的数值仅有一个位数的差异。
 给定一个代表编码总位数的非负整数 n，打印其格雷编码序列。即使有多个不同答案，你也只需要返回其中一种。
 格雷编码序列必须以 0 开头。
 example 1:
     输入: 2
     输出: [0,1,3,2]
     解释:
     00 - 0
     01 - 1
     11 - 3
     10 - 2
     对于给定的n，其格雷编码序列并不唯一。
     例如，[0,2,3,1]也是一个有效的格雷编码序列。
     00 - 0
     10 - 2
     11 - 3
     01 - 1

 example 2:
     输入: 0
     输出: [0]
     解释: 我们定义格雷编码序列必须以 0 开头。
     给定编码总位数为 n 的格雷编码序列，其长度为 2n。当 n = 0 时，长度为 20 = 1。
     因此，当 n = 0 时，其格雷编码序列为 [0]。
"""
from typing import List


# 找规律即可
def gray_code_xor(n: int) -> List[int]:
    result = []
    for i in range(2 ** n):
        result.append((i >> 1) ^ i)
    return result


# 格雷码公式
def gray_code_02(n: int) -> List[int]:
    return [item ^ item >> 1 for item in range(1 << n)]


if __name__ == '__main__':
    print(gray_code_xor(2))
    print(gray_code_xor(0))
    print(gray_code_02(2))
    print(gray_code_02(0))